lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/grafos/ford_fulkerson.cpp

   1 /*
   2   cap[i][j] = Capacidad de la arista (i, j).
   3   prev[i] = Predecesor del nodo i en un camino de aumentación.
   4  */
   5 int cap[MAXN+1][MAXN+1], prev[MAXN+1];
   6
   7 vector<int> g[MAXN+1]; //Vecinos de cada nodo.
   8 inline void link(int u, int v, int c){ cap[u][v] = c; g[u].push_back(v), g[v].push_back(u); }
   9 /*
  10   Notar que link crea las aristas (u, v) && (v, u) en el grafo g. Esto es necesario
  11   porque el algoritmo de Edmonds-Karp necesita mirar el "back-edge" (j, i) que se crea
  12   al bombear flujo a través de (i, j). Sin embargo, no modifica cap[v][u], porque se
  13   asume que el grafo es dirigido. Si es no-dirigido, hacer cap[u][v] = cap[v][u] = c.
  14  */
  15
  16
  17 /*
  18   Método 1:
  19
  20   Mantener la red residual, donde residual[i][j] = cuánto flujo extra puedo inyectar
  21   a través de la arista (i, j).
  22
  23   Si empujo k unidades de i a j, entonces residual[i][j] -= k y residual[j][i] += k
  24   (Puedo "desempujar" las k unidades de j a i).
  25
  26   Se puede modificar para que no utilice extra memoria en la tabla residual, sino
  27   que modifique directamente la tabla cap.
  28 */
  29
  30 int residual[MAXN+1][MAXN+1];
  31 int fordFulkerson(int n, int s, int t){
  32   memcpy(residual, cap, sizeof cap);
  33
  34   int ans = 0;
  35   while (true){
  36     fill(prev, prev+n, -1);
  37     queue<int> q;
  38     q.push(s);
  39     while (q.size() && prev[t] == -1){
  40       int u = q.front();
  41       q.pop();
  42       vector<int> &out = g[u];
  43       for (int k = 0, m = out.size(); k<m; ++k){
  44         int v = out[k];
  45         if (v != s && prev[v] == -1 && residual[u][v] > 0)
  46           prev[v] = u, q.push(v);
  47       }
  48     }
  49
  50     if (prev[t] == -1) break;
  51
  52     int bottleneck = INT_MAX;
  53     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  54       bottleneck = min(bottleneck, residual[u][v]);
  55     }
  56     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  57       residual[u][v] -= bottleneck;
  58       residual[v][u] += bottleneck;
  59     }
  60     ans += bottleneck;
  61   }
  62   return ans;
  63 }
  64
  65
  66
  67 /*
  68   Método 2:
  69
  70   Mantener la red de flujos, donde flow[i][j] = Flujo que, err, fluye
  71   de i a j. Notar que flow[i][j] puede ser negativo. Si esto pasa,
  72   es lo equivalente a decir que i "absorve" flujo de j, o lo que es
  73   lo mismo, que hay flujo positivo de j a i.
  74
  75   En cualquier momento se cumple la propiedad de skew symmetry, es decir,
  76   flow[i][j] = -flow[j][i]. El flujo neto de i a j es entonces flow[i][j].
  77
  78 */
  79
  80 int flow[MAXN+1][MAXN+1];
  81 int fordFulkerson(int n, int s, int t){
  82   //memset(flow, 0, sizeof flow);
  83   for (int i=0; i<n; ++i) fill(flow[i], flow[i]+n, 0);
  84   int ans = 0;
  85   while (true){
  86     fill(prev, prev+n, -1);
  87     queue<int> q;
  88     q.push(s);
  89     while (q.size() && prev[t] == -1){
  90       int u = q.front();
  91       q.pop();
  92       vector<int> &out = g[u];
  93       for (int k = 0, m = out.size(); k<m; ++k){
  94         int v = out[k];
  95         if (v != s && prev[v] == -1 && cap[u][v] > flow[u][v])
  96           prev[v] = u, q.push(v);
  97       }
  98     }
  99
 100     if (prev[t] == -1) break;
 101
 102     int bottleneck = INT_MAX;
 103     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
 104       bottleneck = min(bottleneck, cap[u][v] - flow[u][v]);
 105     }
 106     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
 107       flow[u][v] += bottleneck;
 108       flow[v][u] = -flow[u][v];
 109     }
 110     ans += bottleneck;
 111   }
 112   return ans;
 113 }
 114